Absorbers seen in the spectrum of background quasars are a unique tool to select HI-rich galaxies at all redshifts. In turns, these allow to determine the cosmological evolution of the HI gas, Omega_HI+HeII, a possible indicator of gas consumption as star formation proceeds. The Damped Lyman-alpha systems (DLAs with N(HI) > 10^20.3 cm^-2), in particular, are believed to contain a large fraction of the HI gas but there are also indications that lower column density systems, named ``sub-Damped Lyman-alpha'' systems play a role at high-redshift. Here we present the discovery of high-redshift sub-DLAs based on 17 z>4 quasar spectra observed with the Ultraviolet-Visual Echelle Spectrograph (UVES) on VLT. This sample is composed of 21 new sub-DLAs which, together with another 10 systems from previous ESO archive studies, make up a homogeneous sample. The redshift evolution of the number density of several classes of absorbers is derived and shows that all systems seem to be evolving in the redshift range from z=5 to z~3. This is further used to estimate the redshift evolution of the characteristic radius of these classes of absorbers assuming a Holmberg relation and one unique underlying parent population. DLAs are found to have R_* ~ 20 h_100^-1 kpc, while sub-DLAs have R_* ~ 40 h_100^-1 kpc. The redshift evolution of the column density distribution, f(N,z), down to N(HI) = 10^19 cm^-2 is also presented. A departure from a power law due to a flattening of f(N,z) in the sub-DLA regime is present in the data. f(N,z) is further used to determine the HI gas mass contained in sub-DLAs at z>2. The complete sample shows that sub-DLAs are important at all redshifts from z=5 to z=2. Finally, the possibility that sub-DLAs are less affected by the effects of dust obscuration than classical DLAs are discussed.